﻿namespace LearnDSSortings;

public class MergeSort
{
    public void Sort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int mid = (right - left) / 2 + left;
            Sort(arr, left, mid);
            Sort(arr, mid + 1, right);
            Merge(arr, left, mid, right);
        }
    }

    public void Merge(int[] arr, int left, int mid, int right)
    {
        int i = left;
        int j = mid + 1;
        int k = left;
        int[] B = new int [right + 1];
        while (i <= mid && j <= right)
        {
            if (arr[i] < arr[j])
            {
                B[k] = arr[i];
                i = i + 1;
            }
            else
            {
                B[k] = arr[j];
                j = j + 1;
            }

            k = k + 1;
        }

        while (i <= mid)
        {
            B[k] = arr[i];
            i++;
            k++;
        }

        while (j <= right)
        {
            B[k] = arr[j];
            j++;
            k++;
        }

        for (int x = left; x < right; x++)
        {
            arr[x] = B[x];
        }
    }

    private void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}